package com.sjf.day02.tree;

import java.util.Arrays;

/**
 * 堆排序
 *  大顶堆 -》 数组升序
 *  小顶堆 -》 数组降序
 *  <pre>
 *      先找到第一个非叶子节点，然后比较两个叶子节点的大小，将较大的与当前节点交换
 *      保存较大节点的下标，并将temp(最开始保存非叶子节点的变量)赋值给较大节点的位置
 *      此时非叶子节点索引-1(由于是完全二叉树，叶子节点的顺序总是依次-1的)
 *      继续上述操作，堆顶的节点值是最大的
 *      此时进行交换操作,让数组下标为0的数和数组尾部交换(即将最大值放到末尾)
 *      j--的操作是将最大值隔离出去，下次循环只对 0~j-1操作(即无序数组)
 *      循环调用toHeap()方法，每次将最大值放到堆顶与无序数组尾部交换来完成对数组的排序
 *  </pre>
 * @author <huangtang>
 * @since 2022/1/7 10:11
 **/
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4,6,-1,95,8,5,23,9};
        //创建海量arr数据排序
        //int[] arr = new int[10000000];
        //for (int i = 0; i < 10000000; i++) {
        //    arr[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        //}
        //long t1 = System.currentTimeMillis();
        heapSort(arr);
        //System.out.println((System.currentTimeMillis()-t1));
    }

    public static void heapSort(int[] arr){
        System.out.println("堆排序");

        //System.out.println("分步完成");
        //toHeap(arr,1,arr.length);
        //System.out.printf("第一次: %s \n", Arrays.toString(arr)); //4,9,8,5,6
        //                                            //     4
        //                                            //   9   8
        //                                            // 5  6
        //toHeap(arr,0,arr.length);
        //System.out.printf("第二次: %s", Arrays.toString(arr)); //9,6,8,5,4
                                                   //     9
                                                   //   6   8
                                                   // 5  4

        //一次完成
        for(int i = arr.length/2-1;i>=0;i--){
            toHeap(arr,i, arr.length);
        }

        //将堆顶元素 和 数组末尾元素交换
        for(int j = arr.length-1;j>0;j--){
            //交换
            swap(arr,0,j);
            toHeap(arr,0,j);
        }

        System.out.printf("数组 %s",Arrays.toString(arr));

    }

    /**
     * 将二叉树转为大顶堆
     * 小堆顶只需要修改比较符号即可
     * @param arr 调整的二叉树数组
     * @param i 表示非叶子节点在数组中的索引
     * @param length 对多少个元素进行调整
     *  <pre>
     *    length每次都会减少，堆顶的数总是会和末尾的交换
     *  </pre>
     */
    public static void toHeap(int[] arr,int i,int length){

        int temp = arr[i];//先取出非叶子节点的元素,保存到临时变量
        //k = i*2+1指的是i的左子节点
        for(int k = i*2+1;k<length;k = k*2+1){
            if(k+1 < length && arr[k] < arr[k+1]){ //说明左子节点小于右子节点
                k = k+1;//让k指向右子节点
            }
            if(arr[k] > temp){ //如果子节点大于父节点
                arr[i] = arr[k]; //把较大的值赋给非叶子节点
                i = k; //k 赋值给i，继续循环比较
            }else{
                break;
            }
        }
        //循环结束，将以i为父节点的最大值，放在了树的树顶
        arr[i] = temp; //将temp放在调整后的位置
    }

    public static void swap(int[] a, int i, int j) {
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }
}
